package lc.q51_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Q56 {

    public int[][] merge(int[][] intervals) {
        // 首先将第一位排序
        if (intervals.length == 0) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparingInt(r -> r[0]));

        int[] c = intervals[0];
        List<int[]> results = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            final int[] ints = intervals[i];
            if (ints[0] > c[1]) {
                results.add(c);
                c = ints;
            } else {
                c = new int[] {c[0], Math.max(c[1],ints[1])};
            }
        }
        results.add(c);
        int[][] ints = new int[results.size()][];
        for (int i = 0; i < results.size(); i++) {
            ints[i] = results.get(i);
        }
        return ints;
    }

}
